/**
 * 
 */
package com.gwcloud.leetcode.interview100;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @ClassName   : Leetcode0378 
 * @author      : ganwei 
 * @date        : 2020年5月30日
 * @Description : Leetcode0378
 */
public class Leetcode0378 {
	/**
	 * -解题思路，最大堆解法
	 */
    public int kthSmallest(int[][] matrix, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer integer, Integer t1) {
                return t1 - integer;
            }
        });
        for (int i = 0 ; i < matrix.length; i++){
            for (int j = 0; j < matrix[0].length; j++){
                queue.add(matrix[i][j]);
                if (queue.size() > k)
                {
                    queue.poll();
                }

            }

        }
        return queue.peek();
    }
	/**
	 * -解题思路，二分查找
	 */
    public int kthSmallest_1(int[][] matrix, int k){
    	int n = matrix.length-1;
    	int left = matrix[0][0], right = matrix[n][n];
    	while(left < right){
    		int mid = left + (right-left) / 2;
    		int count = countNotMoreThanMid(matrix, mid, n);
    		if(count < k){
    			left = mid+1;
    		}else{
    			right = mid;
    		}
    	}
    	return left;
    }
    public int countNotMoreThanMid(int[][] matrix, int mid, int n){
    	int count = 0;
    	int x = 0, y = n;
    	while(x <= n && y >= 0){
    		if(matrix[y][x] <= mid){
    			count += y+1;
    			x++;
    		}else{
    			y--;
    		}
    	}
    	return count;
    }
    
    
    /**
     * -主函数
     */
    public static void main(String[] args){
    	
    }
}
